package com.sun;

import java.util.HashMap;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/valid-parentheses/
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 *  左括号必须用相同类型的右括号闭合。
 *  左括号必须以正确的顺序闭合。
 *  每个右括号都有一个对应的相同类型的左括号。
 */
public class Test20有效的括号 {
    public static void main(String[] args) {
        String s1 = "(){}[]";
        String s2 = "(()[])";
        String s3 = "({[]})";
        String s4 = "([))";
        String s5 = "){";
        String s6 = "[({(())}[()])]";
        String s7 = "()";
        boolean valid1 = isValid2(s5);
        System.out.println(valid1);
    }

    /**
     * 方法1：自己
     */
    public static boolean isValid1(String s) {
        boolean isValid = true;
        HashMap<Character, Integer> map1 = new HashMap<>(){{
            put('[',0); put('{',0); put('(',0);
        }};
        HashMap<Character,Character> map2 = new HashMap<>(){{
            put('[',']');put('{','}');put('(',')');
        }};
        HashMap<Character,Character> map3 = new HashMap<>(){{
            put(']','[');put('}','{');put(')','(');
        }};
        if (s.length() %2 != 0 || map3.get(s.charAt(0)) != null){
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            Character close = map2.get(c);
            if (close != null){
                map1.put(c,map1.get(c)+1);
            }else {//c为右括号
                Character last = s.charAt(i-1);
                Character start = map3.get(c);
                if(map1.get(start) == 0){
                    return false;
                } else if (map2.get(last) != null &&
                        !start.equals(last)){//前一个为左括号，并且和start不等
                   return false;
                } else if (map3.get(last) != null &&
                        (c.equals(last) || map1.get(map3.get(last)) != 0)){
                    //前一个为右括号，并且(和c不等 || 该右括号的左括号数不为0)
                    return false;
                }else {
                    map1.put(start,map1.get(start)-1);
                }
            }
        }
        if (map1.get('[') != 0 || map1.get('{') != 0 || map1.get('(') != 0){
            return false;
        }
        return  isValid;
    }

    /**
     * 方法2 ：自己根据力扣官方
     */
    public static boolean isValid2(String s) {
        if (s.length() %2 !=0){
            return false;
        }
        HashMap<Character,Character> map2 = new HashMap<>(){{
            put('[',']');put('{','}');put('(',')');
        }};
        HashMap<Character,Character> map3 = new HashMap<>(){{
            put(']','[');put('}','{');put(')','(');
        }};
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map2.get(c) != null){
                stack.push(c);
            }else {
                if (stack.empty()) return false;
                if (stack.pop() != map3.get(c)){
                    return false;
                }
            }
        }
        return stack.empty();
    }

    /**
     * 方法3：力扣官方
     */
    public static boolean isValid3(String s) {
        if(s.length()%2 != 0) return false;
        HashMap<Character,Character> map = new HashMap<>(){{
            put(']','[');put('}','{');put(')','(');
        }};
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                if(stack.empty() || stack.pop() != map.get(ch)){
                    return false;
                }
            }else {
                stack.push(ch);
            }
        }
        return stack.empty();
    }
}
